/*
 * @lc app=leetcode.cn id=139 lang=cpp
 *
 * [139] 单词拆分
 *
 * https://leetcode-cn.com/problems/word-break/description/
 *
 * algorithms
 * Medium (52.84%)
 * Likes:    1563
 * Dislikes: 0
 * Total Accepted:    285.5K
 * Total Submissions: 539.4K
 * Testcase Example:  '"leetcode"\n["leet","code"]'
 *
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 *
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 *
 *
 * 示例 2：
 *
 *
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
 * 注意，你可以重复使用字典中的单词。
 *
 *
 * 示例 3：
 *
 *
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= s.length <= 300
 * 1 <= wordDict.length <= 1000
 * 1 <= wordDict[i].length <= 20
 * s 和 wordDict[i] 仅有小写英文字母组成
 * wordDict 中的所有字符串 互不相同
 *
 *
 */

// @lc code=start
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    bool wordBreak(string s, vector<string> &wordDict) {
        // 自己的解法，能够正常通过
        /* int n = s.length();
        vector<int> dp(n, 0);
        vector<int> index_1;
        index_1.push_back(-1);
        unordered_set<string> hash;
        for (auto &word : wordDict) {
            hash.insert(word);
        }
        // i为s下标，对应的dp[i]
        for (int i = 0; i < n; ++i) {
            for (auto &index : index_1) {
                if (hash.find(s.substr(index + 1, i - index)) != hash.end()) {
                    dp[i] = 1;
                }
            }
            if (dp[i] == 1) {
                index_1.push_back(i);
            }
        }
        return dp[n-1] > 0; */

        // 官解
        int n=s.length();
        vector<bool> dp(n+1,false);
        dp[0]=true;
        for(int i=1;i<=n;++i){
            for(const string &word:wordDict){
                int len=word.length();
                if(i>=len&&s.substr(i-len,len)==word)
            }
        }
    }
};
// @lc code=end
